package com.leetcode.offer.chapter5;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/15 16:23
 */
public class FirstUniqChar_50 {

    public char firstUniqChar(String s) {
        char[] chars = s.toCharArray();
        // 只有小写字母，那么可以创建一个26位的布尔数组用来标识元素是否已经出现过
        boolean[] showed = new boolean[26];
        Set<Character> set = new LinkedHashSet<>();
        for (char ch : chars) {
            int index = ch - 'a';
            // 如果含有元素那么直接删除元素
            if (set.contains(ch)) set.remove(ch);
                // 没有出现过才会加入到集合
            else if (!showed[index]) set.add(ch);
            showed[index] = true;
        }
        // 为空返回空字符，否则返回迭代器的第一个
        // 这里通过LinkedHashSet的特性保证了加入的顺序
        return set.isEmpty() ? ' ' : set.iterator().next();
    }

    public char firstUniqChar2(String s) {
        char[] chars = s.toCharArray();
        // 数组用于存储索引。即字符第一次出现的位置
        int[] indice = new int[26];
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            // 这里保存的是索引值+1，与初始赋值的0区分开来
            if (indice[index] == 0) indice[index] = i + 1;
                // 字符已经出现过一次，那么置为-1
            else if (indice[index] > 0) indice[index] = -1;
        }
        int first = Integer.MAX_VALUE;
        // 找到最小的索引
        for (int index : indice) {
            if (index > 0) first = Math.min(first, index);
        }

        // 如果不存在最小索引那么返回空字符，否则返回的是chars[first-1]位置的字符
        // 因为最开始赋值的是索引值+1，取的时候要进行-1
        return first == Integer.MAX_VALUE ? ' ' : chars[first - 1];
    }

}
